package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 2/1/21 11:17 AM
 *
 * https://leetcode-cn.com/problems/fair-candy-swap/
 *
 */
public class _888_公平的糖果棒交换 {

    public int[] fairCandySwap(int[] A, int[] B) {

        int[] res = new int[2];

        Arrays.sort(A);
        Arrays.sort(B);

        int sumA = 0, sumB = 0;

        for (int val : A) {

            sumA += val;
        }

        for (int val : B) {

            sumB += val;
        }

        int instance = sumB - sumA;

        if (instance == 0) {

            return res;
        }

        int lenB = B.length;

        for (int a:A) {

        /**
         *
         * * 可以使用二分法
        * int newIntance = (b - a) << 1; if (newIntance == instance) {
        *
        * <p>res[0] = a; res[1] = b; return res; }
        */

            int left = 0, right = lenB;

            while (left < right) {

                int mid = ((right - left) >> 1) + left;

                int newDis = (B[mid] - a) << 1;

                if (newDis == instance) {

                    res[0] = a;
                    res[1] = B[mid];
                    return res;
                }else if (newDis < instance) {

                    left = mid + 1;
                }else if (newDis > instance) {

                    right = mid;
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {


//        int[] num1 = new int[]{35,17,4,24,10};
//        int[] num2 = new int[]{63,21};
        int[] num1 = new int[]{2};
        int[] num2 = new int[]{1,3};
        _888_公平的糖果棒交换 candy = new _888_公平的糖果棒交换();

        int[] res = candy.fairCandySwap(num1, num2);
        System.out.println(Arrays.toString(res));
    }
}
